
package com.algorithm.code.string;

import java.util.Arrays;

/**
 * Strings
 */
public class Strings {

    private static final int SIZE = 256;

    /**
     * DM 算法实现-散列表
     * 
     * @param b   : 模式串
     * @param m   : 模式串长度
     * @param bc: 散列表. 采用字符在ascii码表中的位置作为下标
     */
    private void generateBC(char[] b, int m, int[] bc) {
        Arrays.fill(bc, -1);
        for (int i = 0; i < m; i++) {
            int ascii = (int) b[i];
            // 由于是按照顺序处理的，
            bc[ascii] = i;
        }
    }

    /**
     * bm算法
     * 
     * @param a:主串
     * @param n    : main string length j
     * @param b    : pattern string
     * @param m    : pattern string length
     * @return int:
     */
    private int bm(char[] a, int n, char[] b, int m) {

        int[] bc = new int[SIZE];

        /*
         * 采用模式串构建坏字符哈希表
         */
        this.generateBC(b, m, bc);

        int i = 0; // i 表示主串与模式串匹配的第一个字符

        while (i <= n - m) {
            int j;
            // j 为模式串的最后一个字符
            // 模式串从后向前匹配
            for (j = m - 1; j >= 0; --j) {
                // 坏字符的位置
                // 坏字符在主串中位置:i+j
                // 坏字符在模式串中位置:j
                if (b[j] != a[i + j]) {
                    break;
                }
            }

            if (j < 0) {
                return i; // 匹配成功
            }

            i = i + (j - bc[(int) a[i + j]]);
        }
        return -1;
    }

    /**
     * BF算法的另一种实现
     * 
     * @param mainString
     * @param pattern
     * @return
     */
    private final int bfMatch2(final String mainString, final String pattern) {

        final int mainStringLength = mainString.length();
        final int patternLength = pattern.length();

        int i = 0, j = 0;

        while (i < mainStringLength) {

            while (j < patternLength && mainString.charAt(i) == pattern.charAt(j)) {
                ++i;
                ++j;
            }

            if (j >= patternLength) {
                return i - j;
            }

            // 回退指针
            i = i - j + 1;
            j = 0;
        }
        return -1;

    }

    /**
     * BF match实现 BF match 算法其实就是暴力检索算法
     * 
     * @param mainString
     * @param pattern
     * @return
     */
    private final int bfMatch(final String mainString, final String pattern) {

        final int mainStringLength = mainString.length();
        final int patternLength = pattern.length();

        int i = 0, j = 0;

        while (i < mainStringLength && j < patternLength) {

            if (mainString.charAt(i) == pattern.charAt(j)) {
                ++i;
                ++j;
            } else {
                // i和j指针回退
                j = 0;
                i = i - j + 1;

            }
        }

        if (j >= patternLength) {
            return i - j;
        }

        return -1;
    }

    /**
     * 算法第四版中的实现
     * 
     * @param txt
     * @param pat
     * @return
     */
    private final int bf(String txt, String pat) {

        int m = pat.length(), n = txt.length();

        for (int i = 0; i <= n - m; ++i) {

            int j;
            for (j = 0; j < m; ++j) {
                if (txt.charAt(j + i) != pat.charAt(j)) {
                    break;
                }
            }

            if (j == m) {
                //找到，说明j走过了模式串的长度
                return i;
            }

        }
        return -1;
    }

    public static void main(final String[] args) {

        final Strings strings = new Strings();
        System.out.println(strings.bfMatch2("12344", "44"));
        System.out.println(strings.bfMatch("12344", "44"));
        System.out.println(strings.bf("12344", "44"));

    }
}